/**
 * //Given a non-empty array nums containing only positive integers, find if the
 * //array can be partitioned into two subsets such that the sum of elements in both
 * //subsets is equal.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: nums = [1,5,11,5]
 * //Output: true
 * //Explanation: The array can be partitioned as [1, 5, 5] and [11].
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: nums = [1,2,3,5]
 * //Output: false
 * //Explanation: The array cannot be partitioned into equal sum subsets.
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= nums.length <= 200
 * // 1 <= nums[i] <= 100
 * //
 * //
 * // Related Topics 数组 动态规划 👍 1426 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00416PartitionEqualSubsetSum {
    public static void main(String[] args) {
        Solution solution = new ID00416PartitionEqualSubsetSum().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean canPartition(int[] nums) {
            boolean res = false;
            int sum = arraySum(nums);
            if (nums.length == 1 || sum % 2 != 0) return false;

            int target = sum / 2;

            //假设把所有元素一次判断放到左边后，左边的和
            boolean[][] state = new boolean[nums.length][target + 1];
            boolean[] status = new boolean[target + 1];
//        state[0][0] = true;
//        //头一个元素就可能超过target
//        if(nums[0] < target){
//            state[0][nums[0]] = true;
//        }

            status[0] = true;
            if (nums[0] < target) {
                status[nums[0]] = true;
            }

            if (nums[0] == target) {
                return true;
            }

            for (int i = 1; i < nums.length; ++i) {

                if (target - nums[i] == 0) {
                    return true;
                }
                for (int j = target - nums[i]; j >= 0; --j) {

                    if (status[j]) {
                        if (j + nums[i] < target) {
                            status[j + nums[i]] = true;
                        }
                        if (j + nums[i] == target) {
                            return true;
                        }
                    }


//                if(state[i-1][j]){ //根据前一步判断
//                    //不放
//                    state[i][j] = true;
//                    //放
//                    if(j + nums[i] < target){
//                        state[i][j+nums[i]] = true;
//                    }
//                    //能达到，跳出
//                    if(j + nums[i] == target){
//                        return true;
//                    }
//
//                }

                }


            }


            return res;


        }

        public int arraySum(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            return sum;

        }


    }
//leetcode submit region end(Prohibit modification and deletion)


}